home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / pc / CODECS.ZIP / codecs / francais / dcodlzw.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-10-13  |  15.2 KB  |  401 lines
  1. /* Fichier: dcodlzw.c
  2.    Auteur: David Bourgin
  3.    Date de creation: 14/2/94
  4.    Date de derniere mise a jour: 12/10/95
  5.    Dessein: Exemple de decodage LZW avec comme donnees a decompresser le contenu d'un fichier.
  6. */
  7.  
  8. #include <stdio.h>
  9. /* Pour les routines printf,fgetc,fputc. */
  10. #include <stdlib.h>
  11. /* Pour la routine exit. */
  12.  
  13. /* Codes d'erreur renvoyes a l'appelant */
  14. #define NO_ERROR             0
  15. #define BAD_FILE_NAME        1
  16. #define BAD_ARGUMENT         2
  17. #define BAD_MEM_ALLOC        3
  18. #define BAD_DATA_CODE        4
  19. #define DICTIONARY_OVERFLOW  5
  20.  
  21. /* Constantes pratiques */
  22. #define FALSE 0
  23. #define TRUE  1
  24.  
  25. /* Variables globales */
  26. FILE *f_source,*f_dest;
  27.  
  28.                              /* Puisque fgetc=EOF uniquement apres un acces
  29.                                 alors statut_octet_stocke vaut TRUE si un octet a ete engrange par fgetc
  30.                                 ou FALSE s'il n'y aucun octet valide, deja lu et non traite dans val_octet_stocke. */
  31. int statut_octet_stocke=FALSE;
  32. int val_octet_stocke;
  33.  
  34. /* Pseudo procedures. */
  35. #define fin_des_donnees() (statut_octet_stocke?FALSE:!(statut_octet_stocke=((val_octet_stocke=fgetc(f_source))!=EOF)))
  36. #define lire_octet()  (statut_octet_stocke?statut_octet_stocke=FALSE,(unsigned char)val_octet_stocke:(unsigned char)fgetc(f_source))
  37. #define ecrire_octet(octet)  ((void)fputc((octet),f_dest))
  38.  
  39. unsigned long int val_a_ecrire=0,
  40.                   val_a_lire=0;
  41. unsigned char nb_bits_a_ecrire=0,
  42.               nb_bits_a_lire=0;
  43.  
  44. typedef struct s_chainage_dic { unsigned int carac;
  45.                                 struct s_chainage_dic *precedent;
  46.                               } t_chainage_dic,*p_chainage_dic;
  47. #define CARAC_CHAINAGE(dic)  ((*(dic)).carac)
  48. #define PREC_CHAINAGE(dic)  ((*(dic)).precedent)
  49.  
  50. #define CODAGE_TYPE_GIF
  51. /* Implique l'inclusion des codes des marqueurs code_initialisation et code_fin_information.
  52.    Pour invalider cette option, mettre la ligne #define... en commentaire. */
  53. #ifdef CODAGE_TYPE_GIF
  54. #define AUTO_DIC_REINIT
  55. /* Si cette macro est definie, le dictionnaire est toujours augmente
  56.    (quitte a creer une erreur de debordement!).
  57.    Si au contraire, cette macro est indefinie, le dictionnaire n'est plus mis a jour
  58.    des que celui-ci atteint sa capacite maximale. C'est la reception du code
  59.    'code_initialisation' qui forcera le dictionnaire a etre vide.
  60.    Pour invalider cette option, mettre la ligne #define... en commentaire.
  61.    Cette macro est observee que si CODAGE_TYPE_GIF est defini,
  62.    ce qui explique la presence des lignes #ifdef... et #endif... */
  63. #endif
  64.  
  65. unsigned int index_dic;
  66. /* Nombre de mots deja reconnus dans le dictionnaire. */
  67. unsigned char nb_bits_decodage;
  68. /* Nombre de bits en decodage. */
  69.  
  70. #define EXP2_DIC_MAX  12
  71. /* 2^EXP2_DIC_MAX donne le nombre maximum de mots dans le dictionnaire durant *toutes* les compressions.
  72.    Valeurs possibles: 3 a 25.
  73.    Attention: Au-dela de 12, vous pouvez avoir des erreurs d'allocations de memoire
  74.    selon votre compilateur et votre ordinateur. */
  75. unsigned int index_dic_max;
  76. /* index_dic_max donne le nombre maximum de mots dans le dictionnaire durant *une* compression.
  77.    Cette constante est limitee entre code_fin_information et 2^EXP2_DIC_MAX */
  78. unsigned char nb_bits_sortie,
  79. /* Nombre de bits pour chaque donnee en sortie.
  80.    Avec nb_bits_sortie=1, on peut compresser/decompresser des images monochromes
  81.    et avec nb_bits_sortie=8, on peut coder des images en 256 couleurs ou des fichiers quelconques. */
  82.               nb_bits_decodage_min;
  83. /* Nombre de bits pour coder code_initialisation. */
  84. unsigned int code_initialisation;
  85. unsigned int code_fin_information;
  86. /* code_initialisation et code_fin_information sont deux codes consecutifs
  87.    qui arrivent juste apres le dernier mot connu du dictionnaire initial. */
  88.  
  89. p_chainage_dic dictionnaire[1<<EXP2_DIC_MAX];
  90.  
  91. void init_dictionnaire1()
  92. /* Parametres en sortie: Aucun.
  93.    Action: Initialise le dictionnaire qui va servir au chainage LZW.
  94.    Erreurs: Aucune s'il y a assez de place memoire.
  95. */
  96. { register unsigned int i;
  97.  
  98.   index_dic_max=1<<12;       /* Attention: Valeurs possibles: 2^3 a 2^EXP2_DIC_MAX */
  99.   nb_bits_sortie=8;          /* Attention: Valeurs possibles 1 a EXP2_DIC_MAX-1
  100.                                 (en general, pour des images a fixer a 1 ou 4 ou 8 si on a
  101.                                 une image monochrome ou en 16 couleurs ou en 256 couleurs). */
  102.   if (nb_bits_sortie==1)
  103.      nb_bits_decodage_min=3;
  104.   else nb_bits_decodage_min=nb_bits_sortie+1;
  105.   code_initialisation=1<<(nb_bits_decodage_min-1);
  106. #ifdef CODAGE_TYPE_GIF
  107.   code_fin_information=code_initialisation+1;
  108. #else
  109.   code_fin_information=code_initialisation-1;
  110. #endif
  111.   for (i=0;i<index_dic_max;i++)
  112.       { if ((dictionnaire[i]=(p_chainage_dic)malloc(sizeof(t_chainage_dic)))==NULL)
  113.            { while (i)
  114.              { i--;
  115.                free(dictionnaire[i]);
  116.              }
  117.              fclose(f_source);
  118.              fclose(f_dest);
  119.              exit(BAD_MEM_ALLOC);
  120.            }
  121.         if (i<code_initialisation)
  122.            CARAC_CHAINAGE(dictionnaire[i])=i;
  123.         PREC_CHAINAGE(dictionnaire[i])=NULL;
  124.       }
  125.   index_dic=code_fin_information+1;
  126.   nb_bits_decodage=nb_bits_decodage_min;
  127. }
  128.  
  129. void init_dictionnaire2()
  130. /* Parametres en sortie: Aucun.
  131.    Action: Reinitialise le dictionnaire qui va servir au chainage LZW.
  132.    Ce dictionnaire doit deja avoir ete initialise par 'init_dictionnaire1'.
  133.    Erreurs: Aucune.
  134. */
  135. { register unsigned int i;
  136.  
  137.   for (i=code_initialisation;(i<index_dic_max)&&(dictionnaire[i]!=NULL);i++)
  138.       PREC_CHAINAGE(dictionnaire[i])=NULL;
  139.   index_dic=code_fin_information+1;
  140.   nb_bits_decodage=nb_bits_decodage_min;
  141. }
  142.  
  143. void supprimer_dictionnaire()
  144. /* Parametres en sortie: Aucun.
  145.    Action: Supprime le dictionnaire qui a servi au chainage LZW.
  146.    Erreurs: Aucune si le dictionnaire a ete initialise par 'init_dictionnaire1'.
  147. */
  148. { register unsigned int i;
  149.  
  150.   for (i=0;(i<index_dic_max)&&(dictionnaire[i]!=NULL);i++)
  151.       free(dictionnaire[i]);
  152. }
  153.  
  154. void ecrire_sortie(valeur)
  155. /* Parametres en sortie: Aucune.
  156.    Action: Ecrit nb_bits_sortie via la fonction ecrire_octet.
  157.    Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme.
  158. */
  159. unsigned int valeur;
  160. { val_a_ecrire=(val_a_ecrire << nb_bits_sortie) | valeur;
  161.   nb_bits_a_ecrire += nb_bits_sortie;
  162.   while (nb_bits_a_ecrire>=8)
  163.         { nb_bits_a_ecrire -= 8;
  164.           ecrire_octet((unsigned char)(val_a_ecrire >> nb_bits_a_ecrire));
  165.           val_a_ecrire &= ((1 << nb_bits_a_ecrire)-1);
  166.         }
  167. }
  168.  
  169. void completer_sortie()
  170. /* Parametres en sortie: Aucune.
  171.    Action: Complete le dernier octet a ecrire par des bits a 0, si necessaire.
  172.    Cette procedure est a considerer avec la procedure ecrire_sortie.
  173.    Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme.
  174. */
  175. { if (nb_bits_a_ecrire>0)
  176.      ecrire_octet((unsigned char)(val_a_ecrire << (8-nb_bits_a_ecrire)));
  177.   val_a_ecrire=nb_bits_a_ecrire=0;
  178. }
  179.  
  180. void ecrire_chainage(chainage,carac)
  181. /* Parametres en sortie: 'carac' peut avoir ete modifie.
  182.    Action: Envoie la chane dans le flux de sortie donne par le 'chainage' du dictionnaire LZW.
  183.    'carac' contient en fin de routine le premier caractere de la chaine.
  184.    Erreurs: Aucune (sauf debordement possible de la pile operationnelle allouee par
  185.    le programme qui doit permettre au moins 8*INDEX_DIC_MAX octets, ce qui correspond
  186.    a un cas de figure exceptionnel.
  187. */
  188. p_chainage_dic chainage;
  189. unsigned int *carac;
  190. { if (PREC_CHAINAGE(chainage)!=NULL)
  191.      { ecrire_chainage(PREC_CHAINAGE(chainage),carac);
  192.        ecrire_sortie(CARAC_CHAINAGE(chainage));
  193.      }
  194.   else { ecrire_sortie(CARAC_CHAINAGE(chainage));
  195.          *carac=CARAC_CHAINAGE(chainage);
  196.        }
  197. }
  198.  
  199. unsigned int ecrire_chaine(code_prec,code_actuel,premier_carac)
  200. /* Parametres en sortie: Renvoie un octet.
  201.    Action: Ecrit la chaine d'octets associee a 'code_actuel' et renvoie
  202.    le premier caractere de cette chaine.
  203.    Erreurs: Aucune.
  204. */
  205. unsigned int code_prec,code_actuel;
  206. unsigned int premier_carac;
  207. { unsigned int carac;
  208.  
  209.   if (code_actuel<index_dic)
  210.      ecrire_chainage(dictionnaire[code_actuel],&carac);
  211.   else { ecrire_chainage(dictionnaire[code_prec],&carac);
  212.          ecrire_sortie(premier_carac);
  213.        }
  214.   return carac;
  215. }
  216.  
  217. void ajouter_chaine(code,premier_carac)
  218. /* Parametres en sortie: Aucun.
  219.    Action: Ajoute au dictionnaire la chaine avec le 'code' donne.
  220.    Erreurs: Aucune.
  221. */
  222. unsigned int code;
  223. unsigned int premier_carac;
  224. { CARAC_CHAINAGE(dictionnaire[index_dic])=premier_carac;
  225.   PREC_CHAINAGE(dictionnaire[index_dic])=dictionnaire[code];
  226.   index_dic++;
  227.   if (index_dic+1==(1<<nb_bits_decodage))
  228.      nb_bits_decodage++;
  229. }
  230.  
  231. unsigned int lire_code_gd()
  232. /* Parametres en sortie: Renvoie la valeur d'un code.
  233.    Action: Renvoie la valeur codee sur 'nb_bits_decodage' bits dans le flux de codes d'entree.
  234.    Les bits sont inscrits de gauche a droite. Exemple: aaabbbbcccc est ecrit:
  235.    Bits     7 6 5 4 3 2 1 0
  236.    Octet 1  a a a b b b b c
  237.    Octet 2  c c c ? ? ? ? ?
  238.    Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme.
  239. */
  240. { unsigned int code_lu;
  241.  
  242.   while (nb_bits_a_lire<nb_bits_decodage)
  243.         { val_a_lire=(val_a_lire<<8)|lire_octet();
  244.           nb_bits_a_lire += 8;
  245.         }
  246.   nb_bits_a_lire -= nb_bits_decodage;
  247.   code_lu=val_a_lire>>nb_bits_a_lire;
  248.   val_a_lire &= ((1<<nb_bits_a_lire)-1);
  249.   return code_lu;
  250. }
  251.  
  252. unsigned int lire_code_dg()
  253. /* Parametres en sortie: Renvoie la valeur d'un code.
  254.    Action: Renvoie la valeur codee sur 'nb_bits_decodage' bits dans le flux de codes d'entree.
  255.    Les bits sont inscrits de droite a gauche. Exemple: aaabbbbcccc est ecrit:
  256.    Bits     7 6 5 4 3 2 1 0
  257.    Octet 1  c b b b b a a a
  258.    Octet 2  ? ? ? ? ? c c c
  259.    Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme.
  260. */
  261. { unsigned int code_lu;
  262.  
  263.   while (nb_bits_a_lire<nb_bits_decodage)
  264.         { val_a_lire |= ((unsigned long int)lire_octet())<<nb_bits_a_lire;
  265.           nb_bits_a_lire += 8;
  266.         }
  267.   nb_bits_a_lire -= nb_bits_decodage;
  268.   code_lu=val_a_lire & ((1<<nb_bits_decodage)-1);
  269.   val_a_lire >>= nb_bits_decodage;
  270.   return code_lu;
  271. }
  272.  
  273. void decodagelzw()
  274. /* Parametres en sortie: Aucun.
  275.    Action: Decompresse suivant la methode de LZW tous les octets lus par les fonctions 'lire_code_??'.
  276.    (ou '??' est 'gd' ou 'dg' selon la facon dont vous stockiez les bits dans le flux compresse.
  277.    Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme.
  278. */
  279. { unsigned int code_prec,code_actuel;
  280.   unsigned int premier_carac;
  281.  
  282.   if (!fin_des_donnees())
  283.      { init_dictionnaire1();
  284.        code_actuel=lire_code_gd();
  285. #ifdef CODAGE_TYPE_GIF
  286.        if (code_actuel!=code_initialisation)
  287.           { fprintf(stderr,"Fichier de codes invalide!\n");
  288.             supprimer_dictionnaire();
  289.             fclose(f_source);
  290.             fclose(f_dest);
  291.             exit(BAD_DATA_CODE);
  292.           }
  293.        if ((code_actuel=lire_code_gd())<code_initialisation)
  294.           { premier_carac=ecrire_chaine(code_prec,code_actuel,premier_carac);
  295.             code_prec=code_actuel;
  296.             code_actuel=lire_code_gd();
  297.           }
  298.        while (code_actuel!=code_fin_information)
  299.              { if (code_actuel==code_initialisation)
  300.                   { init_dictionnaire2();
  301.                     code_actuel=lire_code_gd();
  302.                     if (code_actuel<code_initialisation)
  303.                        { premier_carac=ecrire_chaine(code_prec,code_actuel,premier_carac);
  304.                          code_prec=code_actuel;
  305.                          code_actuel=lire_code_gd();
  306.                        }
  307.                   }
  308.                else { if (code_actuel>index_dic)
  309.                        { fprintf(stderr,"Fichier de codes invalide!\n");
  310.                          fclose(f_source);
  311.                          fclose(f_dest);
  312.                          exit(BAD_DATA_CODE);
  313.                        }
  314. #ifdef AUTO_DIC_REINIT
  315.                       if (index_dic==index_dic_max)
  316.                          { fprintf(stderr,"Depassement de capacite du dictionnaire!\n");
  317.                            fclose(f_source);
  318.                            fclose(f_dest);
  319.                            exit(DICTIONARY_OVERFLOW);
  320.                          }
  321.                       premier_carac=ecrire_chaine(code_prec,code_actuel,premier_carac);
  322.                       ajouter_chaine(code_prec,premier_carac);
  323.                       code_prec=code_actuel;
  324.                       code_actuel=lire_code_gd();
  325. #else
  326.                       premier_carac=ecrire_chaine(code_prec,code_actuel,premier_carac);
  327.                       if (index_dic<index_dic_max)
  328.                          ajouter_chaine(code_prec,premier_carac);
  329.                       code_prec=code_actuel;
  330.                       code_actuel=lire_code_gd();
  331. #endif
  332.                     }
  333.           }
  334.     supprimer_dictionnaire();
  335. #else
  336.        code_prec=code_actuel;
  337.        premier_carac=ecrire_chaine(code_prec,code_actuel,premier_carac);
  338.        while ((!fin_des_donnees())||(nb_bits_a_lire>=nb_bits_decodage))
  339.              { code_actuel=lire_code_gd();
  340.                if (code_actuel>index_dic)
  341.                   { fprintf(stderr,"Fichier de codes invalide!\n");
  342.                     fclose(f_source);
  343.                     fclose(f_dest);
  344.                     exit(BAD_DATA_CODE);
  345.                   }
  346.                premier_carac=ecrire_chaine(code_prec,code_actuel,premier_carac);
  347.                if (index_dic==index_dic_max-2)
  348.                   { init_dictionnaire2();
  349.                     if ((!fin_des_donnees())||(nb_bits_a_lire>=nb_bits_decodage))
  350.                        { code_prec=(code_actuel=lire_code_gd());
  351.                          premier_carac=ecrire_chaine(code_prec,code_actuel,premier_carac);
  352.                        }
  353.                   }
  354.                else ajouter_chaine(code_prec,premier_carac);
  355.                code_prec=code_actuel;
  356.              }
  357.        supprimer_dictionnaire();
  358. #endif
  359.        completer_sortie();
  360.      }
  361. }
  362.  
  363. void aide()
  364. /* Parametres en sortie: Aucun.
  365.    Action: Affiche l'aide du programme et termine son execution.
  366.    Erreurs: Aucune.
  367. */
  368. { printf("Cet utilitaire permet de decompresser un fichier par la methode de LZW\n");
  369.   printf("telle qu'elle est exposee dans 'La Video et Les Imprimantes sur PC'\n");
  370.   printf("\nUsage: dcodlzw source destination\n");
  371.   printf("source: Nom du fichier a decompresser\n");
  372.   printf("destination: Nom du fichier decompresse\n");
  373. }
  374.  
  375. int main(argc,argv)
  376. /* Parametres en sortie: Renvoie un code d'erreur (0=Aucune).
  377.    Action: Procedure principale.
  378.    Erreurs: Detectee, traitee et un code d'erreur est renvoye si necessaire.
  379. */
  380. int argc;
  381. char *argv[];
  382. { if (argc!=3)
  383.      { aide();
  384.        exit(BAD_ARGUMENT);
  385.      }
  386.   else if ((f_source=fopen(argv[1],"rb"))==NULL)
  387.           { aide();
  388.             exit(BAD_FILE_NAME);
  389.           }
  390.        else if ((f_dest=fopen(argv[2],"wb"))==NULL)
  391.                { aide();
  392.                  exit(BAD_FILE_NAME);
  393.                }
  394.             else { decodagelzw();
  395.                    fclose(f_source);
  396.                    fclose(f_dest);
  397.                  }
  398.   printf("Execution de dcodlzw achevee.\n");
  399.   return (NO_ERROR);
  400. }
  401.